# https://www.cnblogs.com/wuxinyan/p/8615127.html
# 十大经典算法：https://www.cnblogs.com/onepixel/articles/7674659.html
# https://www.cnblogs.com/itsharehome/p/11058010.html
# 冒泡排序
def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    print(arr)


# 选择排序
def selectSort(arr):
    for i in range(len(arr)-1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    print(arr)


# 插入排序
def insertSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        # print(preIndex)
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        arr[preIndex+1] = current
    print(arr)


if __name__ == '__main__':
    arr = [1, 2, 35, 46, 12, 13, 2, 89, 78, 74, 56, 96, 14,
           52, 21, 28, 34, 146, 32, 23, 24, 10, 9, 100, 77, 66, 102, 0]
    bubbleSort(arr)
    selectSort(arr)
    insertSort(arr)
